Wiggle Sort

Posted on   |   In   |  

wiggle sort

Wiggle Sort

Given an unsorted array nums, reorder it in-place such that 
nums[0] <= nums[1] >= nums[2] <= nums[3]....
For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1,     6, 2, 5, 3, 4].

思路一:先将数组排序，然后将index 1跟2交换，3跟4交换…..
时间复杂度O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public void wiggleSort(int[] nums) {
        sort(nums.begin(), nums.end());
        // 将数组中一对一对交换,此处需要注意是i开始结束的位置
        for(int i = 2; i < nums.length; i+=2){
            int tmp = nums[i-1];
            nums[i-1] = nums[i];
            nums[i] = tmp;
        }
    }
}

思路2，直接交换
要满足wiggle sort的条件，那么需要两个条件
nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4] <= …..
如果i是奇数，nums[i] >= nums[i - 1]
如果i是偶数，nums[i] <= nums[i - 1]

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public void wiggleSort(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1]
            if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){
                int tmp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i] = tmp;
            }
        }
    }
}

Wiggle Sort ii

link
题目:Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

分析:看到这道题目第一想法就是排序，找到中位数，从中位数处分成两部分，每次从这两部分中取出一个数，构成一个上面的序列对代码如下，会超时。
过程如下:

nums        1 5 1 1 6 4
排序         1 1 1 4 5 6
分成两部分    1 1 1|4 5 6
            .     .
依次取出    1 4 1 5 1 6

1
2
3
4
5
6

vector<int> temp(nums);
sort(temp.begin(), temp.end());
for(int i = temp.size() - 1, j =0 , k = i/2 + 1; i >= 0; i--){
        nums[i] = temp[(i & 1) ?k++:i++];
}

优化算法:在前面的wiggle Sort中，允许等号，而ii中是没有等号的
既然是将数组分成两部分，一部分小于另一部分，很自然的想到基于快排的寻找第k数的算法，这个算法的平均时间复杂度是$\Theta(n)$
思路为:
1.寻找中位数
2.three-way-partion,也就是荷兰国旗问题
wiki Dutch national flag problem
这里说明以下这个三分法的原理:
详细分析过程摘自
问题转换为：给定数组A[0…N-1]，元素只能取0、1、2三个值，设计算法，使得数组排列成“00…0011…1122…22”的形式。
借鉴快速排序中partition的过程。定义三个指针：begin=0、current=0、end=N-1：
1、当A[cur]==2，则A[cur] 与A[end]交换，end–，cur不变
2、当A[cur]==1，则cur++，begin不变，end不变
3、当A[cur]==0，则：
3.1、若begin==cur，则begin++，cur++
3.2、若begin≠cur，则A[cur]与A[begin]交换，begin++，cur不变
three way partition
通过上面的图我们可以发现，[begin,cur]区间维护的是的是等于1的元素区间，而begin之前的元素一定是0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
procedure three-way-partition(A : array of values, mid : value):
    begin ← 0
    cur ← 0
    end ← size of A - 1

    while cur ≤ end:
        if A[cur] < mid:
            swap A[left] and A[cur]
            left ← left + 1
            cur ← cur + 1
        else if A[cur] > mid:
            swap A[cur] and A[end]
            end ← end - 1
        else:
            cur ← cur + 1

具体分析为:原始的数组为
| | | | | | | ||
|:—-|:—-|:—|:—|:|:|:—–|
|index|0 |1 |2 |3|4|5|
|value|1 |5 |1 |1|6|4|

在这里会将原始数组的数字移动来满足要求,change表示原数组的对应的位置在wiggle Sort之后所在的位置
| | | | | | | ||
|:—- |:—-|:—|:—|:|:|:—–|
|index |0|1|2|3|4|5|
|change|1|3|5|0|2|4|
从中发现了规律:

change = (2*index + 1)%(arr.size | 1)

接下来我们用three way partition来交换数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define index(i)    nums[(2* i + 1) % (len | 1)]
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        size_t len = nums.size();
        auto medianIter = nums.begin() + len/2;
        nth_element(nums.begin(), medianIter, nums.end());
        
        int median = *medianIter;
        
        //Three way 
        int left = 0, current = 0, right = len-1;
        while(current <= right){
            if(index(current) > median)
                std::swap(index(left++), index(current++));
            else if(index(current) < median)
                std::swap(index(current), index(right--));
            else
                current++;
        }
    }
};

sort colors

link
其实就是上面的荷兰国旗问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0, cur = 0, right = nums.size() - 1;
        
        while(cur <= right){
            if(nums[cur] == 0)
                swap(nums[left++],nums[cur++]);
            else if(nums[cur] == 2)
                swap(nums[cur],nums[right--]);
            else
                cur++;
        }
    }
};